//面试题 02.06. 回文链表
//此方法可以做到时间复杂度为O(n),空间复杂度为O(1)

#include <stdbool.h>
#include <stdio.h>
struct ListNode {
	int val;
	struct ListNode* next;
};
struct ListNode* getMid(struct ListNode* head)
{
    struct ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode* prev = NULL, * cur = head;
    while (cur)
    {
        struct ListNode* next = cur->next;
        //头插
        cur->next = prev;
        prev = cur;
        //迭代
        cur = next;
    }
    return prev;//因为是头插，所以返回prev
}
bool isPalindrome(struct ListNode* head) {
    //1.找到链表的中间结点
    struct ListNode* mid = getMid(head);
    //2.从中间结点开始往后逆置
    struct ListNode* rmid = reverse(mid);
    //3.对比
    while (rmid)
    {
        if (rmid->val != head->val)
            return false;
        //迭代
        rmid = rmid->next;
        head = head->next;
    }
    return true;
}